package progect_01;

import java.util.ArrayList;

public class TreeSort {
	public static void main(String[] args) {
		//二叉排序树--7, 3, 10, 12, 5, 1, 9
		int[] arr= {5,3,7,1,4,6,8,0,2,9};
		ArrayList<Node> list=new ArrayList<>();
		for(int i=0;i<arr.length;i++) {
			list.add(new Node(arr[i]));
		}
		BinarySortTree rooTree=new BinarySortTree(list.get(0));
		for(int i=1;i<list.size();i++) {
			rooTree.CreBinarySortTree(list.get(i));
		}
		//前序遍历
		rooTree.PreOrderPrint();
		System.out.println("删除两棵子树结点");
		rooTree.DelNode(5);
		System.out.println("删除后遍历");
		rooTree.PreOrderPrint();
		
	}
	
}
class BinarySortTree{
	private Node rootNode;
	
	public BinarySortTree(Node rootNode) {
		this.rootNode=rootNode;
	}
	//前序遍历
	public void PreOrderPrint() {
		if(rootNode==null) {
			return;
		}else {
			rootNode.PreOrder();
		}
	}
	
	
	//创建二叉排序树
	public void CreBinarySortTree(Node node) {
		if(rootNode==null) {
			rootNode=node;
		}else {
			rootNode.add(node);
		}
		
	}
	//查找要删除的目标结点
	public Node GetDelTarget(int data) {
		if(rootNode!=null) {
			return rootNode.GetDelNode(data);
		}
		else {
			return null;
		}
		
	}
	//获取要删除结点的根节点
	public Node GetDelParent(int data) {
		if(rootNode==null) {
			return null;
		}else{
			return rootNode.GetParentNode(data);
		}
	}
	//获取要替换的结点
	public int GetReplaceNode(Node targetNextNode) {
		//思路：从目标结点的左子树中找最大的那个节点，若左子树还有右子树
		//那么左子树的右子树的结点就是要替换的结点，要没有的话，该左子树就是
		//要替换的结点
		//这里传进来的是目标结点的右子树作为根节点
		Node tempNode=targetNextNode;
		while(tempNode.getRight()!=null) {
			tempNode=tempNode.getRight();
		}
		//到这里已经是做左子树的最后一个右子树结点了--删除（这个就是叶子结点了）
		DelNode(tempNode.getData());//将替换结点删除，值保留（删除的是叶子结点的情况）
		return tempNode.getData();
	
	}
	
	
	//删除节点--主代码块--//分为三种情况：1、删除叶子结点 2、删除有一棵子树的结点 2、删除有两棵子树的结点
	public void DelNode(int data) {
		//获取到要删除的目标结点
		Node targetNode=GetDelTarget(data);
		//获取要删除的目标结点的根节点
		Node parentNode=GetDelParent(data);
		if(targetNode==null) {
			return;
		}
		//分情况
		if(targetNode.getLeft()==null && targetNode.getRight()==null) {
			//要删除的节点是叶子结点
			if(data<parentNode.getData()) {
				//是父节点的左子结点
				parentNode.setLeft(null);
			}else {
				//是父节点的右子结点
				parentNode.setRight(null);
			}
			
		}else if(targetNode.getLeft()!=null && targetNode.getRight()!=null) {
			//删除的结点有两个子树的情况
			int replace=GetReplaceNode(targetNode.getLeft());//获取到替换值
			targetNode.setData(replace);			
			
		}else {
			//删除的结点有一棵子树的情况
			//小注意点--当最后只剩下两个节点的时候，要是把根节点给删除就会报错
			//因为此时根节点没有父节点了
			
			if(targetNode.getLeft()!=null) {
				//目标结点有一棵左子树--把左子树放到目标结点的位置上
				if(parentNode!=null) {
					parentNode.setLeft(targetNode.getLeft());
				}else {
					//此时删除的是根节点
					rootNode=targetNode.getLeft();
				}
			}else {
				//目标结点有一棵右子树
				if(parentNode!=null) {
					parentNode.setRight(targetNode.getRight());
				}else {
					rootNode=targetNode.getRight();
				}
			}
			
			
		}
		
		
		
	}
	
	
}
class Node{
	private int data;
	private Node leftNode;
	private Node rightNode;
	
	//前序遍历
	public void PreOrder() {
		System.out.print(this.getData()+" ");
		if(this.leftNode!=null) {
			this.leftNode.PreOrder();
		}
		if(this.rightNode!=null) {
			this.rightNode.PreOrder();
		}
		
	}
	//找到要删除结点的根节点
	public Node GetParentNode(int data) {
		if((this.leftNode!=null && this.leftNode.data==data) ||(this.rightNode!=null && this.rightNode.data==data)) {
			return this;
		}
		if(data<this.data) {
			//向左找
			if(this.leftNode!=null) {
				return this.leftNode.GetParentNode(data);
			}
		}else {
			//向右找
			if(this.rightNode!=null) {
				return this.rightNode.GetParentNode(data);
			}
		}
		return null;
	}
	
	//找到要删除的目标结点
	public Node GetDelNode(int data) {
		if(this.data==data) {
			return this;
		}
		if(data<this.data) {
			//向左找
			if(this.leftNode!=null) {
				//向左递归查找
				return this.leftNode.GetDelNode(data); 
			}
		}else {
			if(this.leftNode!=null) {
				return this.rightNode.GetDelNode(data);
			}
		}
		return null;
		
	}
	
	
	//添加
	public void add(Node node) {
		//小的在左，大的在右，相同的随便放
		if(this.data>=node.data) {
			//要添加的结点应该放到左边
			if(this.leftNode!=null) {
				this.leftNode.add(node);
			}else {
				this.leftNode=node;
			}
		}else {
			//要添加的结点放到右边
			if(this.rightNode!=null) {
				this.rightNode.add(node);
			}else {
				this.rightNode=node;
			}
		}
		
		
	}
	
	//构造器
	public Node(int data) {
		this.data=data;
	}
	
	public void setData(int data) {
		this.data=data;
	}
	public int getData() {
		return data;
	}
	
	public void setLeft(Node leftNode) {
		this.leftNode=leftNode;
	}
	public Node getLeft() {
		return leftNode;
	}
	public void setRight(Node rightNode) {
		this.rightNode=rightNode;
	}
	public Node getRight() {
		return rightNode;
	}
	
}